Virtual instructors are agents that are capabable of guiding a user until a task
in a virtual world has been completed. They constitute a promising contribution
to many fields, including simulation, training and interactive
games~\cite{kenny07,jan09} but they also pose many challenges. In particular, the
ability to communicate using natural language is important for believable and
effective virtual humans. Such ability has to be good enough to engage the
trainee or the gamer in the activity. Nowadays, most conversational systems
operate on a dialogue-act level and require extensive annotation efforts or hand
writing of thousands of rules in order to be fit for their task~\cite{rieser10}.
Semantic annotation and rule authoring have long been known as bottlenecks for
developing conversational systems for new domains. 

In this paper, we present a novel algorithm for generating virtual instructors
from automatically annotated human-human corpora. Our algorithm, when given a
task-based corpus situated in a virtual world, generates an instructor that
robustly helps a user achieve a given task in the virtual world of the corpus.
There are two main approaches toward automatically producing dialogue utterances.
One is the selection approach, in which the task is to pick the appropriate
output from a corpus of possible outputs. The other is the generation approach,
in which the output is dynamically assembled using some composition procedure,
e.g. grammar rules.  The selection approach to generation has only been used in
conversational systems that are not task-oriented such as negotiating
agents~\cite{gandhe07}, question answering characters~\cite{kenny07}, and virtual
patients~\cite{leuski09}.  To the best of our knowledge, our algorithm is the
first one proposed for doing corpus based generation and interaction management
for task-oriented systems.  

%Our algorithm provides a dialogue model that is predominately system-initiative.  
%The intuition behind our algorithm is that we view the pairs (DG's instruction, 
%DF's reaction) as adjacency pairs. As a result our selection algorithm selects
%the instruction whose corresponding reaction maximized the advance in the task 
%plan according to the corpus. 

The advantages of corpus based generation are many. To start with, it affords the
use of complex and human-like sentences without detailed analysis.  Moreover, the
system may easily use recorded audio clips rather than speech synthesis and
recorded video for animating virtual humans.  Finally, no rule writing by a
dialogue expert or manual annotations is needed.  The disadvantage of corpus
based generation is that the resulting dialogue may not be fully coherent.  For
non-task oriented systems, dialogue management through corpus based methods has
shown coherence related problems. Shawar and Atwell~\cite{shawar03,shawar05}
present a method for learning pattern matching rules from corpora in order to
obtain the dialogue manager for a chat-bot. Gandhe and Traum~\cite{gandhe07b}
investigate several dialogue models for negotiating virtual agents that are
trained on an unannotated human-human corpus. Both approaches report that the
dialogues obtained by these methods are still to be improved because the lack of
dialogue history management results in incoherences. Since in task-based
systems, the dialogue history is restricted by the structure of the task, the
absence of dialogue history management is alleviated by tracking the current
state of the task.
 
In the next section we introduce the corpora used in this paper.
Section~\ref{algorithm} presents the two phases of our algorithm, namely
automatic annotation and dialogue management through selection. In
Section~\ref{virtual-instructor} we present a fragment of an interaction with a
virtual instructor generated using the corpus and the algorithm introduced in the
previous sections. We evaluate the virtual instructor in interactions with human
subjects using objective as well as subjective metrics. We present the results of
the evaluation in Section~\ref{evaluation}. We compare our results with both
human and rule-based virtual instructors hand-coded for the same task. Finally,
Section~\ref{conclusions} discusses the weaknesses of the approach for developing
instruction giving agents, as well as its advantages and drawbacks with respect
to hand-coded systems. In this last section we also discuss improvements on our
algorithms designed as a result of our error analysis.     

  
